Gate-Arrays (GAs) or Field Programmable Gate Arrays (FPGAs) are integrated circuits that are characterized in that a plurality of identical transistors or programmable logic elements is arranged on a chip such that an arbitrary circuit, in most instances a digital circuit, can be realized with only a few wiring levels or configurable connections, respectively.
GAs are wired in accordance with the specific application in the last phase of the semiconductor production process; FPGAs are correspondingly programmed by the user in order to realize their configuration in accordance with the circuit to be implemented.
FPGAs, in particular, realize a combinatorial logic in accordance with the state of the art by utilizing so-called “Look Up Tables” (LUTs). These are ROMs or multiplexers that deliver a certain boolean value for each possible combination of the input values (applied to the address inputs or selection inputs). The advantage of these LUTs is that they make it possible to realize any arbitrary boolean function of the I inputs. The total number of boolean functions (operations) for I inputs is:2(2′) (in words: 2 to (2 to I)).
This correlation descriptively results from a truth table. At I input variables, this truth table has Z=2I lines. Each line may contain the output value “0” or “1” such that any boolean operation is uniquely defined by a binary number with Z digits. Consequently, the total number of boolean operations is 2Z.
Most important the circuit expenditure for a LUT is not linearly proportional to the number of inputs. In the realization in the form of a ROM as well as in the realization in the form of a multiplexer, the expenditure approximately doubles for each additional input, i.e., the circuit expenditure increases exponentially with the number of inputs (FIG. 1).
This is the reason why existing FPGAs only utilize LUTs with no more than 6 inputs. In most instances, LUTs with only 4 inputs are utilized.
In addition, conventional GAs and FPGAs utilize routing structures and channels that allow a so-called Manhattan routing. This model was adopted from a city with streets that are arranged in a grid-shaped pattern and produces connections by linking smaller sections. This solution has the disadvantage that the signal delay on such a connection is highly dependent on the number of serially linked sections. Consequently, the delay time fluctuates significantly on different connections. This is fatal, in particular, for clock lines because the clock skew may increase to such a degree that the circuit function is no longer ensured.